package com.zhugang.week07;

/**
 * @program algorithms
 * @description: lowestCommonAncestorBySearchTree
 * @author: chanzhugang
 * @create: 2022/07/27 12:30
 */
public class LowestCommonAncestorBySearchTree {

    /**
     * 剑指offer 68-I 二叉搜索树的最近公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 根节点大于左子树 && 根节点小于右子树
        // 非递归解法
        TreeNode x = root;
        while (x != null) {
            if (p.val < x.val && q.val < x.val) {
                x = x.left;
            } else if (p.val > x.val && q.val > x.val) {
                x = x.right;
            } else {
                // 包含了各种情况
                return x;
            }
        }
        return null;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}